# -*- coding: utf-8 -*-
from __future__ import print_function

import sys
import os
import copy

# reload(sys)
# sys.setdefaultencoding("utf-8")
"""
 问题：人民币面额分别为1 、5 、10 、20 、50 、100，请设计高效的算法实现任意给定金额X（比如950）有多少种换钱方法，并分析时间复杂度。
 参考链接：https://blog.csdn.net/u011468619/article/details/77883263
"""


def findMoney(target):
    # 时间复杂度分析
    # 主要时间复杂度就在 跑迭代的时候的复杂度
    # 假设：1.找零备选人民币面额数量为  N；当前题干为：6
    #      2.目标金额为M
    # 时间复杂度为： O(N*M*M) = O(N*M^2)

    # 特殊情况提前判断
    if target <= 1 or target != int(target):
        return 0

    money_list = [1, 5, 10, 20, 50, 100]

    # 初始化一个数组
    dp = [[0] * (target+1) for _ in money_list]



    # 初始化第一行和第一列
    for i in range(len(dp)):
        dp[i][0] = 1

    for i in range(target + 1):
        if i % money_list[0] == 0:
            dp[0][i] = 1
        else:
            dp[0][i] = 0

    # 开始遍历
    for i in range(1, len(money_list)):
        money = money_list[i]
        print(money)
        for j in range(1, target+1):
            tmp = 0
            k = 0
            while k * money <= j:
                tmp += dp[i - 1][j - k * money]
                k += 1
            dp[i][j] = tmp
    # 测试
    for tmp in dp:
        print(tmp)

    return dp[-1][-1]

print(findMoney(5))